home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / cug172 / dfa.c < prev    next >
C/C++ Source or Header  |  1986-02-05  |  6KB  |  213 lines
  1. /*
  2.   HEADER: CUG     nnn.nn;
  3.   TITLE:     LEX - A Lexical Analyser Generator
  4.   VERSION:     1.0 for IBM-PC
  5.   DATE:      Jan 30, 1985
  6.   DESCRIPTION:     A Lexical Analyser Generator. From UNIX
  7.   KEYWORDS:     Lexical Analyser Generator YACC C PREP
  8.   SYSTEM:     IBM-PC and Compatiables
  9.   FILENAME:      DFA.C
  10.   WARNINGS:     This program is not for the casual user. It will
  11.          be useful primarily to expert developers.
  12.   CRC:         N/A
  13.   SEE-ALSO:     YACC and PREP
  14.   AUTHORS:     Scott Guthery 11100 leafwood lane Austin, TX 78750
  15.   COMPILERS:     DESMET-C
  16.   REFERENCES:     UNIX Systems Manuals
  17. */
  18. /*
  19.  * Copyright (c) 1978 Charles H. Forsyth
  20.  *
  21.  * Modified 02-Dec-80 Bob Denny -- Conditionalize debug code for reduced size
  22.  * Modified 29-May-81 Bob Denny -- Clean up overlay stuff for RSX.
  23.  * More     19-Mar-82 Bob Denny -- New C library & compiler
  24.  * More     03-May-82 Bob Denny -- Final touches, remove unreferenced autos
  25.  * More     29-Aug-82 Bob Denny -- Clean up -d printouts
  26.  * More     29-Aug-82 Bob Denny -- Reformat for readability and comment
  27.  *                                 while learning about LEX.
  28.  * More        20-Nov-83 Scott Guthery -- Adapt for IBM PC & DeSmet C
  29.  */
  30.  
  31. /*
  32.  *    *********
  33.  *    * DFA.C *
  34.  *    *********
  35.  *
  36.  * LEX -- DFA construction routines
  37.  */
  38.  
  39. #include <stdio.h>
  40. #include "lexlex.h"
  41.  
  42. extern struct set *eclosure();          /* Used only by DFA */
  43. extern struct dfa *defalt();            /* Used only by DFA */
  44. extern struct move *stbase();           /* Used only by DFA */
  45.  
  46. /*
  47.  * Build the DFA from the NFA
  48.  */
  49. dfabuild()
  50.    {
  51.    struct trans *trp;
  52.    struct nfa **vec, **tp, *np, *temp[MAXNFA+1];
  53.    int a, i;
  54.    struct set **sp, *stack[MAXDFA], **spp, *xp;  /* DFA set stack */
  55.    struct dfa *state;                  /* --> current DFA state */
  56.    struct xset *xs, *xse;
  57.  
  58.   /*
  59.    * Simulate an epsilon transition from nfa state 0 to
  60.    * the initial states of the machines for each
  61.    * translation.
  62.    */
  63.    nfa[0].n_char = EPSILON;            /* Set NFA state 0 transition EPSILON */
  64.    /*
  65.     * Allocate a state vector, each node of which will
  66.     * point to an NFA starting state.  Each translation
  67.     * generates an NFA, so the number of translations
  68.     * equals the number of NFA start states.
  69.     */
  70.    vec = lalloc(i = (transp-trans)+1, sizeof(*vec), "dfabuild");
  71.    /*
  72.     * Fill in the start state vector
  73.     */
  74.    vec[0] = nfa;                       /* vec[0] always --> NFA state 0 */
  75.    for (a = 1, trp = trans; trp < transp; trp++)  /* For each translation */
  76.       vec[a++] = trp->t_start;         /* Pick up the NFA start state */
  77.    /*
  78.     * Now build the set sp --> e-CLOSURE(vec)
  79.     */
  80.    sp = eclosure(newset(vec, i, 1));
  81.  
  82.    free(vec);                          /* Deallocate the start state vector */
  83.  
  84.    /*
  85.     * At this point state 0 of the DFA is constructed.
  86.     * This is the start state of the DFA.
  87.     * Mark it "added" and push it on to the stack.
  88.     */
  89.    sp->s_flag |= ADDED;
  90.    spp = stack;
  91.    *spp++ = sp;
  92.    /*
  93.     * From state 0, which is now stacked, all further DFA
  94.     * states will be derived.
  95.     */
  96.    while (spp > stack)
  97.       {
  98.       sp = *--spp;
  99.       for (a = 0; a < NCHARS; a++)
  100.          insets[a] = 0;
  101.       xse = sets;
  102.       for (i = 0; i < sp->s_len; i++)
  103.          xse = addset(sp->s_els[i], xse);
  104.       state = newdfa();
  105.       sp->s_state = state;
  106.       state->df_name = sp;
  107. #ifdef DEBUG
  108.       if (lldebug)
  109.          {
  110.          fprintf(lexlog, "build state %d ", state-dfa);
  111.          pset(sp, 1);
  112.          fprintf(lexlog, "\n");
  113.          }
  114. #endif
  115.       state->df_ntrans = xse-sets;
  116.       for (xs = sets; xs < xse; xs++)
  117.          {
  118.          a = xs->x_char&0377;
  119.          tp = temp;
  120.          for (i = 0; i < sp->s_len; i++)
  121.             if ((np = sp->s_els[i])->n_char==a ||
  122.                 np->n_char==CCL &&
  123.                 np->n_ccl[a/NBPC]&(1<<(a%NBPC)))
  124.                add(temp, &tp, np->n_succ[0]);
  125.          xp = newset(temp, tp-temp, 1);
  126.          xp = eclosure(xp);
  127. #ifdef DEBUG
  128.          if (lldebug)
  129.             {
  130.             putc('\t', lexlog);
  131.             chprint(a);
  132.             putc('\t', lexlog);
  133.             pset(xp, 1);
  134.             fprintf(lexlog, "\n");
  135.             }
  136. #endif
  137.          xs->x_set = xp;
  138.          if (xp->s_state==0 && (xp->s_flag&ADDED)==0)
  139.             {
  140.             xp->s_flag |= ADDED;
  141.             if (spp >= stack+MAXDFA)
  142.                {
  143.                error("dfabuild: stack overflow");
  144.  
  145.                exit(1);
  146.                }
  147.             *spp++ = xp;
  148.             }
  149.          }
  150.       state->df_default = defalt(state, &xse);
  151.       setbase(state, stbase(xse), xse);
  152.       }
  153.    }
  154.  
  155. /*
  156.  * If an nfa state is not already a member of the vector `base', add it.
  157.  */
  158. add(base, tpp, np)
  159. struct nfa ***tpp, **base, *np;
  160.    {
  161.    register struct nfa **tp;
  162.  
  163.    for (tp = base; tp < *tpp; tp++)
  164.       if (*tp == np)
  165.          return;
  166.    *(*tpp)++ = np;
  167.    }
  168.  
  169. /*
  170.  * Add the character(s) on which state `np' branches to the transition vector.
  171.  */
  172. addset(np, xse)
  173. register struct nfa *np;
  174. struct xset *xse;
  175.    {
  176.    register a;
  177.    register char *ccl;
  178.  
  179.    if ((a = np->n_char) < NCHARS)
  180.       xse = addxset(a, xse);
  181.    if (a != CCL)
  182.       return(xse);
  183.    ccl = np->n_ccl;
  184.    for (a = 0; a < NCHARS; a++)
  185.       if (ccl[a/NBPC]&(1<<(a%NBPC)))
  186.          xse = addxset(a, xse);
  187.    return(xse);
  188.    }
  189.  
  190. /*
  191.  * Add a character to the transition vector, if it isn't there already.
  192.  */
  193. addxset(a, xse)
  194. register a;
  195. struct xset *xse;
  196.    {
  197.    register struct xset *xs;
  198.    register int temp;
  199.    /*
  200.    * VMS native doesn't do this correctly:
  201.    *    if (insets[a]++)
  202.    */
  203.    temp = insets[a];
  204.    insets[a] += 1;
  205.    if (temp)
  206.       return(xse);
  207.    xs = xse++;
  208.    xs->x_char = a;
  209.    xs->x_set = NULL;
  210.    xs->x_defsame = 0;
  211.    return(xse);
  212.    }
  213.